#ifndef _BO2_2_H
#define _BO2_2_H
#include "c2-2.h"
//bo2-2.h 带有头节点的单链表，存储结构由c2-2.h定义，基本操作12个，包括算法2.8~2.10
void InitList(LinkList &L)
{//操作结果 构造一个空的线性表L
    L = (LinkList)malloc(sizeof(LNode));
    if(!L)
        exit(OVERFLOW);
    L->next = NULL;
}

void DestroyList(LinkList &L)
{//初始条件：L已存在。操作结果：销毁线性表L
    LinkList q;
    while(L) // L指向节点非空
    {
        q = L->next; // q指向首元节点
        free(L);//释放头节点
        L = q;//L指向q
    }
}

void ClearList(LinkList L)//不改变L
{//初始条件：L已存在。操作结果：将L重置为空表
    LinkList p = L->next;
    L->next = NULL;
    DestroyList(p);
}

Status ListEmpty(LinkList L)
{//初始条件：L已存在。操作结果：若为空表，返回TRUE 否则返回FALSE
    if(L->next) //非空
        return FALSE;
    else
        return TRUE;
}

int ListLength(LinkList L)
{//初始条件：L已存在。操作结果：返回链表长度
    int count = 0;//计数器初值为0
    LinkList p = L->next; //p指向首元节点
    while(p) //未到表尾
    {
        count++;
        p = p->next;
    }
    return count;
}

Status GetElem(LinkList L, int i, ElemType &e) //严书算法2.8
{//初始条件：L为带头节点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    int j = 1;//j设置为计数器，初值为1
    LinkList p = L->next;//p指向首元节点
    while(p && j < i)//顺着指针向后查找，直到p指向第i个节点或p为空(没找到)
    {
        j++;
        p = p->next;
    }
    if(!p || j > i) // 第i个节点没找到
        return ERROR;
    e = p->data;
    return OK;
}

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{//初始条件：L已存在，compare时数据元素判定函数（满足为1，否则为0）
//操作结果： 返回L中第一个与e满足关系compare（）的数据元素的位序
//          若不存在这样的数据元素，则返回0
    int i = 0; //计数器初值为0
    LinkList p = L->next;
    while(p)
    {
        i++;
        if(compare(p->data,e))
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{//初始条件：L已存在，
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；
//          否则操作失败，pre_e无定义
    LinkList q, p = L->next;
    while(p && p->next)
    {
        q = p->next; //q指向p的后继
        if(q->data == cur_e)
        {
            pre_e = p->data;
            return OK;
        }
        p = q;
    }
    return ERROR;
}

Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
    LinkList p  = L->next;
    while(p && p->next)
    {
        if(p->data==cur_e)
        {
            next_e = p->next->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}

Status ListInsert(LinkList L , int i , ElemType &e)//算法2.9
{//在带头节点的单链表L中第i个位置之前插入元素e
    int j = 0;
    LinkList s , p = L;
    while(p && j < i-1)
    {
        j++;
        p = p->next;
    }
    if(!p || j> i -1 )
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete(LinkList L, int i , ElemType &e)//算法2.10
{//在带头节点的单链表中，删除第i个元素，并用e返回其值
    int j = 0;
    LinkList q, p = L;
    while(p->next && j<i-1)
    {
        j++;
        p = p->next;
    }
    if(!p->next || j>i-1)
        return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

void ListTraverse(LinkList L, void(*visit)(ElemType))
{//visit的形参类型为ElemType，与bo2-1.h的=中相应函数的形参类型ElemType&不同
//初始条件L存在，操作结果：依次对L的每个元素调用函数visit（）
    LinkList p = L->next;
    while(p)
    {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
}

#endif
